from typing import List

from sortedcontainers import SortedList


class Solution:
    _MOD = 10 ** 9 + 7

    def sumSubseqWidths(self, nums: List[int]) -> int:
        """思路计算每一个数作为最小值和最大值分别使用多少次；而后使用最大值和总和减去最小值的总和得到结果"""

        distance_max_left = [0] * len(nums)
        distance_max_right = [0] * len(nums)
        distance_min_left = [0] * len(nums)
        distance_min_right = [0] * len(nums)

        # 计算每个数距离其左侧大于等于它的值有多少、小于等于它的值有多少
        values = SortedList()
        for i, num in enumerate(nums):
            i1 = values.bisect_left(num)
            i2 = values.bisect_right(num)
            distance_min_left[i] = i1
            distance_max_left[i] = i - i2
            values.add(num)

        # 计算每个数距离其右侧大于等于它的值有多少、小于等于它的值有多少
        values = SortedList()
        for i in range(len(nums) - 1, -1, -1):
            num = nums[i]
            i1 = values.bisect_left(num)
            i2 = values.bisect_right(num)
            distance_min_right[i] = i1
            distance_max_right[i] = (len(nums) - i - 1) - i2
            values.add(num)

        print(distance_min_left, distance_max_left)
        print(distance_min_right, distance_max_right)

        # 计算最大值的和、最小值的和
        max_total = 0  # 最大值的和
        min_total = 0  # 最小值的和
        for i in range(len(nums)):
            num = nums[i]
            min_times = pow(2, distance_max_left[i]) * pow(2, distance_max_right[i])
            max_times = pow(2, distance_min_left[i]) * pow(2, distance_min_right[i])
            max_total = (max_total + num * max_times) % self._MOD
            min_total = (min_total + num * min_times) % self._MOD

        return max_total - min_total


if __name__ == "__main__":
    print(Solution().sumSubseqWidths([2, 1, 3]))  # 6

    # 测试用例4/64
    print(Solution().sumSubseqWidths([7, 8, 8, 10, 4]))  # 6
